from typing import List


# 给你一个整数数组 nums 和一个整数 target 。
#  向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
#  例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
#  返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
#
#  示例 1：
# 输入：nums = [1,1,1,1,1], target = 3
# 输出：5
# 解释：一共有 5 种方法让最终目标和为 3 。
# -1 + 1 + 1 + 1 + 1 = 3
# +1 - 1 + 1 + 1 + 1 = 3
# +1 + 1 - 1 + 1 + 1 = 3
# +1 + 1 + 1 - 1 + 1 = 3
# +1 + 1 + 1 + 1 - 1 = 3
#
#  示例 2：
# 输入：nums = [1], target = 1
# 输出：1
#  1 <= nums.length <= 20
#  0 <= nums[i] <= 1000
#  0 <= sum(nums[i]) <= 1000
#  -1000 <= target <= 1000
class Solution:
    def findTargetSumWays2(self, nums: List[int], target: int) -> int:
        """
        解法二:动态规划
        记数组的元素和为sum，添加 - 号的元素之和为 neg(neg 必须是非负整数，即不带符号之和)，则其余添加 + 的元素之和为sum−neg，得到的表达式的结果为
         (sum−neg)−neg = sum−2*neg=target  =>   neg = (sum -target) / 2
        问题转化成在数组nums 中选取若干元素，使得这些元素之和等于 neg 的方案数
        :param nums:
        :param target:
        :return:
        """
        numSize, totalSum = len(nums), sum(nums)
        if (totalSum - target) % 2 != 0 or totalSum < target:
            return 0
        neg = (totalSum - target) // 2
        # dp[i][j] 表示在数组 nums 的前 i 个(nums[0:i])数中选取若干元素，使得这些元素之和等于 j 的方案数
        dp = [[0] * (neg + 1) for _ in range(numSize + 1)]
        dp[0][0] = 1  # nums的一个元素也不选，之和为0，方案数为1
        for i in range(1, numSize + 1):
            curNum = nums[i - 1]
            for j in range(neg + 1):
                # 如果 j < curNum，则不能选 num，此时有 dp[i][j]=dp[i−1][j]
                # 如果 j >= curNum，则
                #     如果不选 curNum，方案数是 dp[i−1][j]，
                #     如果选 curNum，方案数是 dp[i−1][j−curNum]，此时有 dp[i][j] = dp[i−1][j] + dp[i−1][j−num]
                # 综合下来写法如下
                dp[i][j] = dp[i - 1][j]
                if j >= curNum:
                    dp[i][j] += dp[i - 1][j - curNum]
        return dp[-1][-1]

    def findTargetSumWays1(self, nums: List[int], target: int) -> int:
        """
        回溯法，每个元素都有 +/- 两种，一共就有2^n种表达式,枚举所有的表达式，判断最终结果是否是target(超时)
        :param nums:
        :param target:
        :return:
        """
        counts, numSize = 0, len(nums)

        def backTrack(index: int, tmpRes: int) -> None:
            if index == numSize:
                if tmpRes == target:
                    nonlocal counts
                    counts += 1
                return
            backTrack(index + 1, tmpRes + nums[index])  # 尝试当前元素为 + 时
            backTrack(index + 1, tmpRes - nums[index])  # 尝试当前元素为 - 时

        backTrack(0, 0)
        return counts

    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        return self.findTargetSumWays2(nums, target)


if __name__ == "__main__":
    nums, target = [1, 1, 1, 1, 1], 3
    # nums, target = [22, 36, 7, 44, 38, 32, 16, 32, 1, 16, 25, 45, 49, 45, 27, 9, 41, 31, 10, 15], -1  # res = 5975
    # nums, target = [25, 18, 47, 13, 45, 29, 15, 45, 33, 19, 39, 15, 39, 45, 17, 21, 29, 43, 50, 10], -25  # res = 5392
    print(Solution().findTargetSumWays(nums, target))
